import java.util.*;

public class FullTextIndex {
    static class IndexNode{
        Character ch;
        List<Integer> indList;
        IndexNode father;
        Map<Character, IndexNode> children;

        public IndexNode(Character ch) {
            this.ch = ch;
            this.children = new HashMap<>();
        }
    }

    IndexNode head = new IndexNode('^');

    //由于只需要对地址重复的去重，所以不需要自定义hashcode equals
    Map<Character, Set<IndexNode>> nodesMap = new HashMap<>();

    private List<Integer> getNodesInd(List<IndexNode> nodes){
        List<Integer> indArr = new ArrayList<>();
        for (IndexNode node:nodes) {
            indArr.addAll(node.indList);
        }
        return indArr;
    }

    private List<IndexNode> getNodesByChar(Character tmpC, boolean includeTop, boolean isTail){
        Set<IndexNode> nodes = nodesMap.get(tmpC);
        if(nodes == null){ return null; }
        List<IndexNode> probNodes = new ArrayList<>(nodes.size());
        for (IndexNode node:nodes) {
            if((includeTop ? true : node.father != head) && (node.children.isEmpty() == isTail)){
                probNodes.add(node);
            }
        }
        return probNodes;
    }

    private void travelGetGrandChildren(List<IndexNode> res, final IndexNode head, IndexNode tmp){
        if(head == null){return;}
        if(head != tmp && tmp.indList != null) {res.add(tmp);}
        for (IndexNode node:tmp.children.values()) {
            travelGetGrandChildren(res, head, node);
        }
    }

    private IndexNode findNodeAlongStr(String str, IndexNode ptr){
        for (int i = 0; i < str.length(); i++) {
            char tmpC = str.charAt(i);
            IndexNode next = ptr.children.get(tmpC);
            if(next == null) {return null;}
            ptr = next;
        }
        return ptr;
    }

    private List<IndexNode> findStrSufNodes(String str, boolean isTail){
        List<IndexNode> res = new ArrayList<>();
        List<IndexNode> probNodes = getNodesByChar(str.charAt(0), false, isTail);
        if(probNodes == null || probNodes.isEmpty()) {
            return res;
        }
        for (IndexNode node:probNodes) {
            IndexNode tail = findNodeAlongStr(str, node.father);
            if(tail != null && isTail?(tail.indList != null):(!tail.children.isEmpty())){
                res.add(tail);
            }
        }
        return res;
    }

    public List<Integer> findStr(String str){
        List<Integer> res = new ArrayList<>();
        IndexNode tailNode = findNodeAlongStr(str, head);
        if(tailNode != null && tailNode.indList != null){ res.addAll(tailNode.indList); }
        return res;
    }

    public List<Integer> find_Str(String str){
        return getNodesInd(findStrSufNodes(str, true));
    }

    public List<Integer> findStr_(String str){
        IndexNode tail = findNodeAlongStr(str, head);
        List<IndexNode> nodes = new ArrayList<>();
        travelGetGrandChildren(nodes, tail, tail);
        return getNodesInd(nodes);
    }

    public List<Integer> find_Str_(String str){
        List<IndexNode> nodes = new ArrayList<>();
        List<IndexNode> strSufNodes = findStrSufNodes(str, false);
        for (IndexNode strSufNode:strSufNodes) {
            travelGetGrandChildren(nodes, strSufNode, strSufNode);
        }
        return getNodesInd(nodes);
    }

    public void add(String str, int ind){
        IndexNode tmp = head;
        for (int i = 0; i < str.length(); i++) {
            char tmpC = str.charAt(i);
            IndexNode next = tmp.children.get(tmpC);
            if(next == null){
                next = new IndexNode(tmpC);
                next.father = tmp;
                tmp.children.put(tmpC, next);
            }
            Set<IndexNode> tmpCNodes = nodesMap.get(tmpC);
            if(tmpCNodes == null){
                tmpCNodes = new HashSet<>();
                nodesMap.put(tmpC, tmpCNodes);
            }
            tmpCNodes.add(next);
            tmp = next;
        }
        if(tmp.indList == null) {tmp.indList = new ArrayList<>();}
        tmp.indList.add(ind);
    }



//    public static void main(String[] args) {
//        char[] arr = new char[]{'赵','钱','孙','李','周','吴','郑','王', '冯','陈','褚','卫', '蒋','沈','韩','杨' ,'朱','秦','尤','许', '何','吕'};
//        List<String> strArr = new ArrayList<>();
//        Random random = new Random();
//        int count = 10;
//        for (int i = 0; i < count; i++) {
//            StringBuilder sb = new StringBuilder();
//            for (int j = 0; j < 4; j++) {
//                sb.append(arr[random.nextInt(arr.length)]);
//            }
//            strArr.add(sb.toString());
//        }
//        FullTextIndex index = new FullTextIndex();
//        Map<String, Integer> hashIndex = new HashMap<>();
//
//        long startTime = System.currentTimeMillis();
//        for (int i = 0; i < count; i++) {
//            index.add(strArr.get(i), i);
//        }
//        System.out.println(System.currentTimeMillis() - startTime);
//
//        startTime = System.currentTimeMillis();
//        for (int i = 0; i < count; i++) {
//            index.findStr(strArr.get(i));
//        }
//        System.out.println(System.currentTimeMillis() - startTime);
//
//        startTime = System.currentTimeMillis();
//        for (int i = 0; i < count; i++) {
//            hashIndex.put(strArr.get(i), i);
//        }
//        System.out.println(System.currentTimeMillis() - startTime);
//
//        startTime = System.currentTimeMillis();
//        for (int i = 0; i < count; i++) {
//            hashIndex.get(strArr.get(i));
//        }
//        System.out.println(System.currentTimeMillis() - startTime);
//        index.add("周", 0);
//        index.add("周桐", 21);
//        index.add("周梦海", 48);
//        index.add("周梦军", 49);
//        index.add("周蒙海", 50);
//        index.add("吴玮", 22);
//        System.out.println(index.find_Str("海"));
//        System.out.println(strArr);
//    }
}
